import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.io.Serializable;
import java.io.ObjectInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.ObjectOutputStream;
import java.io.FileOutputStream;

public class DFA implements Serializable{


	/**
	 * 
	 */
	private static final long serialVersionUID = 4685042032019163733L;
	/**
	 * 
	 */
	public DFANode start;
	public String name;
	public Set<DFANode> acceptingStates;
	public Set<DFANode> nonacceptingStates;

	private static Integer nodeCount = 0;
	private static int numTransitions = 0;


	public DFA(NFA nfa){
		this(nfa, "");
	}

	public DFA(DFANode start){
		this.start = start;
	}

	/*
	 * Serializes a DFA
	 */
	public void save(String filename){
		filename +=".dfa";
		try
		{
			FileOutputStream fos = new FileOutputStream(filename);
			ObjectOutputStream  out = new ObjectOutputStream(fos);
			out.writeObject(this);
			out.close();
		}
		catch(IOException ex)
		{}
	}

	public static DFA load(String name){
		System.out.println("Starting dfa load with " + name);
		DFA temp = null;
		try{
			FileInputStream fis = new FileInputStream(name);
			ObjectInputStream in = new ObjectInputStream(fis);
			temp = (DFA)in.readObject();
			in.close();
		}
		catch(IOException ex) {}
		catch (ClassNotFoundException ex){}
		return temp;
	}

	public void renameNodes(){
		int oldNodeCount = nodeCount;
		Queue<DFANode> q = new LinkedList<DFANode>();
		q.add(start);
		DFANode curnode;
		Set<Character> transitions;
		HashMap<Character, ArrayList<Node>> adjList;
		DFANode next;

		while (!q.isEmpty()){
			curnode = q.remove();
			if (curnode.visited) continue;	//Don't visit it again
			curnode.visited = true;
			curnode.name = nodeCount.toString(); //Give everything a unique name
			nodeCount++;
			adjList = curnode.adjList;
			transitions = adjList.keySet();
			for (char c : transitions){
				numTransitions++;
				next = (DFANode)adjList.get(c).get(0);
				if (!next.visited){	//This is a DFA, so <= 1 transition per character
					q.add(next);
				}
			}
		}
		System.out.println("We have " + (nodeCount - oldNodeCount) + " DFA nodes with " + numTransitions + " edges before minimization.");
	}

	public void minimize(ArrayList<String> tokenNames){
		Set<Set<DFANode>> P = new HashSet<Set<DFANode>>();
		Set<Set<DFANode>> Q = new HashSet<Set<DFANode>>();

		Set<DFANode> curset;
		for (String curname : tokenNames){
			curset = new HashSet<DFANode>();
			for (DFANode n : acceptingStates){
				if (n.tokenName.equals(curname)){
					curset.add(n);
				}
			}
			P.add(curset);
			Q.add(curset);
		}

		//P.add(acceptingStates);
		P.add(nonacceptingStates);
		//Q.add(acceptingStates);
		while (!Q.isEmpty()){
			//Choose and remove a set A from Q
			for (Set<DFANode> A : Q){
				Q.remove(A);
				//For each c in the alphabet
				for (char c : NFA.fullRange){

					//Let X be the set of states for which a
					//transition on c leads to a state in A
					Set<DFANode> X = new HashSet<DFANode>();

					X.clear();
					for (DFANode n : acceptingStates){
						if (n.adjList.get(c) != null && A.contains((DFANode)(n.adjList.get(c).get(0)))){
							X.add(n);
						}
					}
					for (DFANode n : nonacceptingStates){
						if (n.adjList.get(c) != null && A.contains((DFANode)(n.adjList.get(c).get(0)))){
							X.add(n);
						}
					}

					//For each set Y in P for which 
					//X intersect Y is nonempty
					Set<Set<DFANode>> newP = new HashSet<Set<DFANode>>();
					newP.clear();
					for (Set<DFANode> Y : P){
						Set<DFANode> XintY = new HashSet<DFANode>();
						Set<DFANode> YminusX = new HashSet<DFANode>();
						XintY.clear();
						YminusX.clear();
						for (DFANode n : Y){
							if (X.contains(n)){
								XintY.add(n);
							}
							else{
								YminusX.add(n);
							}
						}

						if (XintY.isEmpty()){
							newP.add(Y);
							continue; //continue if intersect empty
						}

						//Replace Y in P by the two sets XintY and YminusX
						//P.remove(Y);
						//if (!XintY.isEmpty()){
						newP.add(XintY);
						//}
						if (!YminusX.isEmpty()){
							newP.add(YminusX);
						}


						//If Y is in Q
						if (Q.contains(Y)){
							//Replace Y in Q by XintY and YminusX
							Q.remove(Y);
							Q.add(XintY);
							Q.add(YminusX);
						}
						else{
							//Add the smaller of the two sets to Q
							if (/*XintY.size() != 0 && (*/XintY.size() < YminusX.size()/* || YminusX.size() == 0)*/){
								Q.add(XintY);
							}
							else /*if (YminusX.size() != 0)*/{
								Q.add(YminusX);
							}
						}
					}
					P.clear();
					for (Set<DFANode> Y : newP){
						P.add(Y);
					}
				}
				break;//We only want one set
			}
		}
		System.out.println("Number of nodes in minimized DFA: " + P.size());

		//Now we have equivalence classes in P - form the DFA
		Set<Character> keys;
		DFANode curnode, target, newStart = null;
		int oldNodeCount = nodeCount;
		Set<DFANode> newNodes = new HashSet<DFANode>();
		ArrayList<Node> oldNodes;

		/*
		 * Create all of the new nodes that we'll need
		 */
		for (Set<DFANode> S : P){
			oldNodes = new ArrayList<Node>();
			if (S.isEmpty()) continue;
			
			oldNodes.addAll(S);
			/*for (String curname : tokenNames){
				for (DFANode n : S){
					if (curname.equals(n.tokenName)){
						oldNodes.add(n);
						break;
					}
				}
			}*/
			//System.out.println("S has size " + S.size() + ", and oldNodes has size " + oldNodes.size());
			curnode = new DFANode(oldNodes, nodeCount.toString());
			nodeCount++;
			curnode.accepting = oldNodes.get(0).accepting;
			newNodes.add(curnode);	
			if (S.contains(start)){
				newStart = curnode;
			}
		}

		/*
		 * For each new node, add transitions
		 */
		DFANode repNode;
		for (DFANode n : newNodes){
			repNode = (DFANode)n.NFAnodes.get(0);
			n.tokenName = repNode.tokenName;
			keys = repNode.adjList.keySet();
			for (char c : keys){
				target = (DFANode)repNode.adjList.get(c).get(0);
				for (DFANode next : newNodes){
					if (next.NFAnodes.contains(target)){//Look for the right meta-node
						n.addTransitions(new char[] {c}, next);
						break;
					}
				}
			}
		}
		start = newStart;
	}

	public static boolean isInAlphabet(char c){
		return c >= 33 && c <= 126;		
	}

	public ArrayList<String> runDFA(String input){
		ArrayList<String> ret = new ArrayList<String>();
		char[] in = input.toCharArray();
		DFANode curnode = start;
		char c = 0;
		int tokenStart = 0;
		boolean failed = false;
		for (int i = 0; i <= in.length; i++){

			try{
				c = in[i];
				if (curnode.adjList.get(c) != null){//we have a transition to make
					curnode = (DFANode)curnode.adjList.get(c).get(0);
					failed = false;
				}
				else{//We have nowhere to go - figure out if it's a valid token and we can go on
					if (isInAlphabet(c)){//if it's a printable ascii character, we've failed
						ret.clear();
						ret.add("Failed at character " + i + ".");
						return ret;
					}
					else{//we have whitespace of some sort
						if (curnode.accepting){
							ret.add(curnode.tokenName + ": " + input.substring(tokenStart, i));
						}
						else{//we ended on a non-token
							ret.clear();
							ret.add("Failed at character " + i + ".");
							return ret;
						}
					}
					while (!isInAlphabet(c)){
						
						if (++i >= in.length){
							return ret;
						}
						c = in[i];
					}
					i--;
					tokenStart = i+1;
					curnode = start;
				}
			}
			catch(Exception e){
				if (i >= in.length && curnode.accepting){
					ret.add(curnode.tokenName + ": " + input.substring(tokenStart, i));
					return ret;
				}
				else{
					ret.clear();
					ret.add("Failed at character " + i + ".");
					return ret;
				}

			}
		}


		return ret;
	}

	public DFA(NFA nfa, String name){
		this.name = name;
		acceptingStates = new HashSet<DFANode>();
		nonacceptingStates = new HashSet<DFANode>();


		DFANode S, T;
		Set<Character> alphabet;
		Set<Node> reachable;
		Set<Node> epsclosure = new HashSet<Node>();
		ArrayList<Node> epsClosureAL = new ArrayList<Node>();
		ArrayList<String> nodeNames;
		HashMap<String, DFANode> allNodes = new HashMap<String, DFANode>();


		epsclosure.add(nfa.start);
		reachable = Node.epsClosure(epsclosure);
		epsClosureAL.addAll(reachable);
		java.util.Collections.sort(epsClosureAL);
		DFANode s0closure = new DFANode(epsClosureAL);
		s0closure.marked = false;
		ArrayList<DFANode> Sdfa = new ArrayList<DFANode>();
		Sdfa.add(s0closure);
		allNodes.put(s0closure.name, s0closure);
		int x = 0;
		while (!Sdfa.isEmpty()){
			//System.out.println("Iterations = " + x++ + "Remaining = " + Sdfa.size());
			T = Sdfa.remove(0);
			if (T.marked){
				continue;
			}

			//Determine the relevant alphabet
			alphabet = new HashSet<Character>();
			T.marked = true;
			for (Node n : T.NFAnodes){
				alphabet.addAll(n.adjList.keySet());
			}

			//Determine all reachable nodes on each 
			//character in the relevant alphabet

			for (char c : alphabet){
				reachable = new HashSet<Node>();
				if (c == NFA.EPS_CHAR){//not in the real alphabet
					continue;
				}

				//reachable = Move_NFA(T,c)
				for (int i = 0; i < T.NFAnodes.size(); i++){
					try{
						reachable.addAll(T.NFAnodes.get(i).adjList.get(c));
					}
					catch(Exception e){};
				}

				//eps-closure(Move_NFA(T,c))
				epsclosure = Node.epsClosure(reachable);

				//Get the node name
				epsClosureAL = new ArrayList<Node>();
				/*for (Node n : epsclosure){
					epsClosureAL.add(n);
				}*/
				epsClosureAL.addAll(epsclosure);
				java.util.Collections.sort(epsClosureAL);

				//If S not in Sdfa, add it
				if (!allNodes.containsKey(epsClosureAL.toString())){//If it doesn't already exist
					S = new DFANode(epsClosureAL);
					S.marked = false;
					Sdfa.add(S);
					allNodes.put(S.name, S);
				}
				else{//It already exists - stick it back in
					S = allNodes.get(epsClosureAL.toString());
					if (!S.marked){
						Sdfa.add(S);
					}
				}

				T.addTransitions(new char[] {c}, S);				
			}
		}

		Set<String> DFAnames = allNodes.keySet();
		boolean added;
		for (String curname : DFAnames){
			S = allNodes.get(curname);
			added = false;
			for (Node n : S.NFAnodes){
				if (n.accepting){
					S.accepting = true;
					S.tokenName = n.tokenName;	//Only give a name to accepting states - we don't care otherwise
					acceptingStates.add(S);
					added = true;
					break;
				}
			}
			if (!added){
				nonacceptingStates.add(S);
			}
			/**
			 * mark S a final state in the DFA
			 */
			//allNodes.put(curname, S);
		}
		this.start = s0closure;

	}

	public String toString(){
		String ret = "";
		Character[] transitions = start.adjList.keySet().toArray(new Character[0]);
		ArrayList<Node> targets;
		char c;
		for (int i = 0; i < transitions.length; i++){
			c = transitions[i];
			targets = start.adjList.get(c);
			for (int j = 0; j < targets.size(); j++){
				ret += (c + "->" + targets.get(j).name + ", ");
			}
		}
		return ret;
		
	}

}
